package com.yiwenup.leetcode.offer;

/**
 * https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/
 **/
public class No056_ii {
    /**
     * 执行用时：3 ms, 在所有 Java 提交中击败了80.98%的用户
     * 内存消耗：38.9 MB, 在所有 Java 提交中击败了97.34%的用户
     */
    public int singleNumber(int[] nums) {
        int[] bit = new int[32];

        for (int num : nums) {
            for (int i = 0; i < bit.length; i++) {
                bit[i] += num & 1;
                num >>>= 1;
            }
        }

        int res = 0;
        for (int i = bit.length - 1; i >= 0; i--) {
            res <<= 1;
            res |= bit[i] % 3;
        }

        return res;
    }
}
